package q316_removeDuplicateLetters;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        s.removeDuplicateLetters("ba");
    }
    public String removeDuplicateLetters(String s) {

        // 统计某一个字符是否在栈内出现
        boolean[] vis = new boolean[26];
        // 用来统计每个字符出现的次数
        int[] num = new int[26];

        for (int i = 0; i < s.length(); i++) {
            num[s.charAt(i) - 'a']++;
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            /*
            这里我们将sb视为一个栈
            ===================
            对于一个字符如果其未在栈内出现 那么再对其进行对应操作
            需要了解的是 所维护的栈符合这样的一个条件：
            对于当前i位置的字符 栈内所有的字符都应该小于该字符
            同时需要考虑 如果字符串在后面位置再也没有i位置的字符 那么这个字符是不能弹出的
             */
            if (!vis[ch - 'a']) {
                // 发现有未在栈内出现的字符
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                    // 并且判断sb中有字符 而且sb最后一个字符 比 当前字符大
                    // 先判断栈顶元素 是否还有剩余 如果没有则不能弹出
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        vis[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
                // 记录该字符已经出现
                vis[ch - 'a'] = true;
                // 加入结果集
                sb.append(ch);
            }
            // 并且num中对应数量减1
            num[ch - 'a'] -= 1;
        }
        return sb.toString();

    }

}
